Users of the HiPerCopS IDE can inject hard faults into their systems. These hard faults, also known as `stuck-at' faults, give insights into how the device might perform in harsh environments. Simulating a system on a faulty device can give a designer great confidence in the robustness of his or her creation. 

Before beginning a simulation in the HiPerCopS IDE, the user is required to select a fault avoidance strategy to be used by the automated module mapper. Different fault avoidance strageties implement different algorithms, and it is interesting to note the differences between these algorithms, both in implementation and performance. First, though, it is important to understand the overall concept of fault avoidance.

\section{Fault Avoidance}
As explained in \cite{avizienis_dsc04}, fault tolerance consists of two major tasks: error detection and recovery. Error detection can occur concurrently with system operation, or preemptively while normal service is interrupted. Either way, its purpose is to identify errors within the system and begin the process of recovery. Recovery is further broken down into error handling and fault handling. Error handling takes care of the detected error, while fault handling prevents errors of the same type from occurring in the future. There are four steps included in fault handling: diagnosis, isolation, reconfiguration, and re-initialization. Diagnosis isolates the source of the problem, and isolation removes this source from the system. Reconfiguration redefines the system in a way that avoids the removed source, and re-initialization performs `bookkeeping' by updating affected tables and registers. 

The HiPerCopS IDE is mainly concerned with reconfiguration and re-initialization in MGRH systems. Together, the activities of reconfiguration and re-initialization can be referred to as fault avoidance. In order to focus on fault avoidance, it is necessary to assume that mechanisms for error detection, fault diagnosis, and fault isolation already exist. Fault avoidance can be especially powerful in MGRH systems due to the flexibility and versatility of the general architecture. MGRH systems are particularly well-suited for fault avoidance mechanism implementation because the H-Tree routing scheme eliminates concerns related to routing and communication \cite{robinson_wsu08}.

\section{Placement Algorithms}

If a design tool's structure placement process can be modified to avoid permanent faults on the device, an MGRH architecture will support the reconfiguration aspect of cell-level fault avoidance. A number of placement strategies have been developed to achieve this goal:

\subsection{No Fault Avoidance}
The unmodified placement algorithm serves as a baseline. It makes no attempt to avoid faulty areas of the device. A placement failure occurs if any of the placed structures contain faulty cells. In the simulation software, this is called the Na\"ive algorithm because it is not sensitive to faults on the device.

The Na\"ive algorithm is a reasonable choice when hard faults are not an issue. The algorithm is simple, intuitive, and efficient. However, hard faults are an eventual reality for every microprocessor. Without a more advanced approach to mapping systems to a device, an MGRH architecture has little advantage over a traditional, non-reconfigurable device.

\subsection{Simple Fault Avoidance}
This algorithm does not map structures to faulty areas of the device. Structures are mapped in the order that the user adds them, and a placement failure occurs if no region of contiguous fault-free cells can be found for a given structure. In the simulation software, this is called the Simple algorithm.

Compared to the Na\"ive algorithm, simple fault avoidance is a much more appropriate approach for an MGRH architecture. The Simple algorithm takes advantage of fault location information, which can easily be obtained if the device can perform a cell verification self-test.

\subsection{Size-Aware Fault Avoidance}
Before mapping the structures to the device, this algorithm orders them according to area. This causes the largest structures to be placed first and the smallest structures to be placed last. Besides this difference, this algorithm is identical to the Simple Fault Avoidance approach. In the simulation software, it is referred to as the Sizeaware algorithm.

It makes sense that some kind of ordering be imposed on a group of system structures waiting to be mapped. Hard faults effectively create partitions on a device. A significant number of partitions tends reduce the number of options for mapping large structures. By allowing large structures to be mapped first, areas of the device with high amounts of contiguous, available cells can be utilized efficiently. The smaller structures, then, can be appropriated to the (usually smaller) remaining partitions.

\subsection{Size-Aware Fault Avoidance with Module Rotation}
This algorithm takes Size-Aware Fault Avoidance a step further. If a fault-free placement cannot be found for a given structure, the structure is rotated 90 degrees and placement is attempted again. This approach could improve the probability of successful placement for non-square structures like adders and subtractors. In the simulation software, this is called the Sizeaware-rotate algorithm.

Returning to the concept of partitions, it is unlikely that a group of random faults will create partitions that are all perfectly square. A rectangular partition could have a square structure mapped to it, but this would not be the most efficient use of functional cells. The ideal solution would be to find a rectangular structure of the same dimensions as the partition. Once rectangular structures are considered, though, the problem of orientation arises. A 3 $\times$ 2-cell structure can fit into a 2 $\times$ 3-cell partition, but only if its orientation is changed through rotation. The Sizeaware-rotate algorithm extends the Sizeaware algorithm by adding support for this particular type of situation.

\section{FFT Benchmark}

Since MGRH architectures can be targeted toward DSP applications, consider a 32 $\times$ 32 cell device used to implement a 256-point fast Fourier transform (FFT) system. The FFT requires 364 cells for implementation, or just over a third of the total device area. The structures comprising this type of unit are listed in Table \ref{table:fft}, and one possible layout of the unit is shown in Figure \ref{fig:fft}.

\begin{table}
\caption{FFT structures, dimensions and quantities.}
\centering
\begin{tabular}{l c c}
\hline
Structure & Dimensions & Quantity \\
\hline
multiplier & 4 $\times$ 4 cells & 12 \\ 
memory & 4 $\times$ 4 cells & 8 \\
adder &  1 $\times$ 2 cells & 11 \\
subtractor & 1 $\times$ 2  cells & 11 \\
\hline
\end{tabular}
\label{table:fft}
\end{table}

\begin{figure}
\centering
\includegraphics[scale=0.6]{img/fft}
\caption{FFT system modules}
\label{fig:fft}
\end{figure}

For this experiment, the HiPerCopS IDE system definition and fault specification utilities were used along with the mapping options. In this situation, a `success' refers to a scenario in which an entire system was mapped to a device while avoiding all faults. A `failure' occurs when there is not enough free, functional space on the device to map the entire set of system structures.

This simulation consists of four test cases, one for each of the previously mentioned placement algorithms. Each test case uses its placement algorithm to map a FFT system to a 32 $\times$ 32 cell device. The independent variable is the number of faults injected into the device, which includes all of the integers between 0 and 199. The dependent variable is the percentage of successful system placement, defined by Equation \ref{eq:placementsuccess}.

\begin{equation}  \label{eq:placementsuccess}
P_{success} = \frac{Number\,of\,Successful\,Placements}{Total\,Number\,of\,Placement\,Attempts} \times 100
\end{equation}

The dependent variable is measured for each value of the independent variable. A successful placement involved mapping each structure in a system to a fault-free area of the device. The total number of placement attempts (i.e., the number of trials) at each value of the independent variable is set to 100. This number of trials gives very consistent and repeatable results.

\section{Performance}
The performance of the four placement algorithms is shown in Figure \ref{fig:results}. The mapping success percentage of each algorithm at select points in the experiment is shown in Table \ref{table:results}.

\begin{table}
\caption{Mapping success rates for different numbers of injected faults.}
\centering
\begin{tabular}{l | r r r}
\hline
& \multicolumn{3}{c}{Success rate with:} \\
Algorithm & 80 faults & 100 faults & 120 faults \\
\hline
Na\"ive & 0\% & 0\% & 0\%\\ 
Simple & 100\% & 97\% & 48\%\\
Sizeaware & 100\% & 100\% & 67\%\\
Sizeaware-rotate & 100\% & 99\% & 67\%\\
\hline
\end{tabular}
\label{table:results}
\end{table}

\begin{figure}
\centering
\includegraphics[scale=0.4]{img/results}
\caption{Mapping algorithm success versus faults injected}
\label{fig:results}
\end{figure}

As expected, the No Fault Avoidance approach performed relatively poorly. Even with only two faults injected into the device, the probability of successful placement is reduced to 41\%. The presence of four faults lowers this figure to 13\%, and eleven or more faults makes placement practically impossible. 

The ability to perform Simple Fault Avoidance dramatically increases the chances of successful system placement. In the presence of 97 faults, 99\% of placements were successful. Even with 118 faults on the device, there was a 60\% success rate. When 128 faults were injected, 30\% of the attempts still resulted in full system placement. 

Size-Aware Fault Avoidance outperformed Simple Fault Avoidance, with the ability to achieve 99\% placement success in the presence of 108 faults. This algorithm successfully placed the FFT system 61\% of the time with 127 faults and 25\% of the time with 134 faults. 

Size-Aware Fault Avoidance with structure Rotation did not have a significant advantage over Size-Aware Fault Avoidance. However, it appeared to have more success when the number of faults was very high. The Sizeaware-rotate algorithm was the only one able to achieve a successful mapping when the number of faults on the device was higher than 170. It is hypothesized that this algorithm is more useful when systems have utilize larger non-square structures. The FFT system of this experiment features a number of non-square adders and subtractors, but these structures may be too small to expose any benefits of rotation.